Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра електронних обчислювальних машин Звіт про виконання лабораторної роботи № 5 з курсу „ Моделювання ” Тема: Аналіз генераторів випадкових чисел. Виконав: студент групи КІ-3 Львів – 2005 Мета: Проаналізувати програмні генератори псевдовипадкових чисел Теоретичні відомості: Традиційно програмне забезпечення використовує програмні генератори псевдовипадкових чисел. Принципова відмінність даних генераторів від апаратних полягає в тому, що такі генератори кожного разу генерують ідентичну послідовність. Використання програмних генераторів спричинило багато неправильних результатів в низці наукових робіт [1]. До недоліків таких генераторів слід віднести достатньо невеликий період повторення псевдовипадкової послідовності, наявність низькочастотних кореляцій у генерованій послідовності. Розглянемо декілька підходів до розробки таких генераторів. Використання рекурентних співвідношень вигляду:  EMBED Equation.DSMT4 
  MACROBUTTON MTPlaceRef \* MERGEFORMAT  SEQ MTEqn \h \* MERGEFORMAT ( SEQ MTEqn \c \* ARABIC \* MERGEFORMAT 1) або  EMBED Equation.DSMT4 
  MACROBUTTON MTPlaceRef \* MERGEFORMAT  SEQ MTEqn \h \* MERGEFORMAT ( SEQ MTEqn \c \* ARABIC \* MERGEFORMAT 2) де a, b, с, m – деякі цілі числа. Вибравши довільним чином деякі початкові значення для X, знаходимо кожне наступне число за співвідношеннями  GOTOBUTTON ZEqnNum873805 \* MERGEFORMAT  REF ZEqnNum873805 \! \* MERGEFORMAT (1) або  GOTOBUTTON ZEqnNum719841 \* MERGEFORMAT  REF ZEqnNum719841 \! \* MERGEFORMAT (2). У випадку використання конгруенції  GOTOBUTTON ZEqnNum719841 \* MERGEFORMAT  REF ZEqnNum719841 \! \* MERGEFORMAT (2) всі генеровані числа належать до інтервалу  EMBED Equation.DSMT4 
. Саме такі співвідношення використовуються для реалізації функції rand() – стандартної функції бібліотеки мови С. Такі програмні генератори випадкових чисел мають низку недоліків. Вони формують випадкові числа таким чином, що лише їх молодші біти є більш-менш випадковими. Тому при генеруванні випадкових чисел в інтервалі  EMBED Equation.DSMT4 
 в жодному разі не можна використовувати співвідношення типу  EMBED Equation.DSMT4 
,  MACROBUTTON MTPlaceRef \* MERGEFORMAT  SEQ MTEqn \h \* MERGEFORMAT ( SEQ MTEqn \c \* ARABIC \* MERGEFORMAT 3) оскільки генеровані таким чином випадкові числа характеризуватимуться іншими статистичними характеристиками. В даному випадку необхідно використовувати лише лінійне перетворення, наприклад:  EMBED Equation.DSMT4 
  MACROBUTTON MTPlaceRef \* MERGEFORMAT  SEQ MTEqn \h \* MERGEFORMAT ( SEQ MTEqn \c \* ARABIC \* MERGEFORMAT 4) Генератори випадкових чисел, побудовані на основі вищезгаданих співвідношень, характеризуються тим, що існують кореляції між згенерованими ними послідовностями. Зокрема, коли згенеровані таким чином послідовності k випадкових чисел відобразити у k-вимірному просторі, то відповідні точки не заповнюють весь простір, а лежатимуть на (k-1) вимірних площинах, причому таких площин буде не більше, ніж  EMBED Equation.DSMT4 
. Якщо крім того, коефіцієнти генератора ще й неправильно вибрано, то таких площин буде набагато менше, ніж  EMBED Equation.DSMT4 
 [1].